廣度優先搜尋 (BFS)

解題思路

我們可以使用廣度優先搜尋來解決這個問題。最簡單的方法是使用一個 Pair (node, level) 來表示狀態，其中 node 表示節點，level 表示該節點所在的層數。每當有新節點 enqueue 時，它的 level 值都會比其父節點的 level 值多 1。

最後，我們可以根據每個節點的 level 值對它們進行分類。在分類時，我們可以使用 hash table 來紀錄一個以 level 為 key，以對應節點組成的陣列為 value 的資料結構。當廣度優先搜尋結束後，我們按照 level 從小到大的順序取出所有值，並將它們組成答案回傳即可。

如果要進一步優化空間複雜度，不使用 hash table mapping，只使用一個 node 變數來表示狀態的話，我們可以通過修改廣度優先搜尋的方式來達成。具體的方法如下：

1. 首先，將 root node enqueue。
2. 當 queue 不為空時，執行以下操作：
   • 計算當前 queue 的長度 。
   • 從 queue 中取出 個元素進行展開，然後進入下一次迭代。

這種方法與普通的廣度優先搜尋的區別在於，普通的廣度優先搜尋每次只取出一個元素進行展開，而這裡每次取出 個元素。在上述過程中，第 次迭代就可以得到二元樹的第 層的 個元素。

我們可以通過觀察這個演算法，並歸納出一個循環不變式 (loop invariant)：在第 次迭代之前，queue 中的所有元素都是第 層的所有元素，並且它們按照從左到右的順序排列。我們可以通過數學歸納法證來證明這個循環不變式的正確性：

初始化 (Initialization)：當 時，queue 中只有 root。 root 這是唯一的層數為 的節點。由於只有一個節點，所以它顯然滿足「從左向右排列」的條件。

維持 (Maintenance)：假設當 時，性質成立。也就是說，在第 輪中，被 dequeue 的 個節點是第 層的所有節點，並且它們按照從左到右的順序排列。由於在對樹進行廣度優先搜索時，從第 層的節點擴展出來的節點一定是第 層的節點，並且第 層的節點只能由第 層的節點擴展到。因此，這 個節點可以擴展到下一層的所有 個節點。又由於 queue 具有先進先出（FIFO）的特性，所以如果第 層的節點按照從左到右的順序 dequeue，那麼第 層的節點也會按照從左到右的順序 dequeue。因此，我們已經透過數學歸納法證明了這個循環不變式在 時仍然成立。

終止(Termination)：由於該循環不變式是正確的，所以每次迭代後得到的結果都是當前層次遍歷結果。因此，我們證明了這個演算法是正確的。

別閉門造車，一起準備面試吧！
在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！
我們將幫助您撰寫一份出色的履歷表，讓您在眾多求職者中脫穎而出。我們將為您提供專業的建議和指導，幫助您在履歷上呈現最完美的自己。如果心動的話，就別猶豫啦！趕快把握機會，動動手指投遞履歷吧！立即加入 Line 讀書會，和大家一起實現夢想！

履歷諮詢	加入讀書會 (邀請碼：3601)

程式

class Solution {
    fun levelOrder(root: TreeNode?): List<List<Int>> {
return root?.let {
            val result = mutableListOf<List<Int>>()
            val queue: Queue<TreeNode> = LinkedList()
            queue.offer(root)
            while (queue.isNotEmpty()) {
                val level = mutableListOf<Int>()
                for (i in queue.indices) {
                    val node = queue.poll()
                    level.add(node.`val`)
                    node.left?.let { queue.offer(it) }
                    node.right?.let { queue.offer(it) }
                }
                result.add(level)
            }
            result
        } ?: emptyList()
    }
}

複雜度分析

我們假設樹上所有節點的數量為 。

• 時間複雜度:
  每個節點都會 enqueue 和 dequeue 一次，因此時間複雜度為 。這代表演算法的運行時間與節點數量成正比。

• 空間複雜度:
  在任何時候，queue 中的節點數量都不會超過 個，因此空間複雜度為 。這代表演算法的空間需求也與節點數量成正比。

　更多演算法題解，一起來學習！

別閉門造車，一起準備面試吧！

在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！

履歷諮詢	加入讀書會 (邀請碼：3601)